#include <iostream>
#include <vector>
using namespace std;

int min_time(vector<vector<int>> &persion, int maxw, int status)
{
	if (status == 0) {
		return 0;
	}
	int ans = INT32_MAX;
	for (int s = status, ts = s; s > 0; s = (s - 1) & status, ts = s) {
		int idx = 0, w = 0, t = 0;
		while (ts) {
			if (ts & 1) {
				t = max(persion[idx][0], t);
				w += persion[idx][1];
			}
			ts >>= 1;
			idx++;
		}
		if (w > maxw) {
			continue;
		}
		ans = min(ans, t + min_time(persion, maxw, status ^ s));
	}
	return ans;
}

int min_time(vector<vector<int>> &persion, int maxw)
{
	int n = persion.size();
	vector<int> dp(1 << n, INT32_MAX);
	vector<vector<int>> tw(1 << n);

	for (int s = 0, ts = 0; s < (1 << n); s++, ts = s) {
		int idx = 0, w = 0, t = 0;
		while (ts) {
			if (ts & 1) {
				t = max(persion[idx][0], t);
				w += persion[idx][1];
			}
			ts >>= 1;
			idx++;
		}
		tw[s] = { t, w };
	}

	dp[0] = 0;
	for (int status = 1; status < (1 << n); status++) {
		for (int s = status, ts = s; s > 0; s = (s - 1) & status, ts = s) {
			if (tw[s][1] > maxw) {
				continue;
			}

			dp[status] = min(dp[status], tw[s][0] + dp[status ^ s]);
		}
	}
	return dp.back();
}

int main()
{
	int w, n;
	cin >> w >> n;
	vector<vector<int>> persion;
	for (int i = 0; i < n; i++) {
		int w, t;
		cin >> t >> w;
		persion.push_back({ t, w });
	}

	//cout << min_time(persion, w, (1 << n) - 1) << endl;
	cout << min_time(persion, w) << endl;

	return 0;
}
